package Top101K;

/**
 * @Author quan
 * @Description 合并两个有序数组:给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组
 * 要求：不能新建一个数组，直接将合并的内容存储到A数组即可
 * @Date 2023/11/9 10:59
 */
public class BM87_Merge {
    public static void main(String[] args) {
        int[] arr1 = {1,2,3};
        int[] arr2 = {4,5,6};
        merge(arr1,arr1.length,arr2,arr2.length);

    }
    /**
     * 输入：[1,2,3],[2,5,6]  返回值：[1,2,2,3,5,6]
     * @param arr1 数组1
     * @param m 数组1的元素个数
     * @param arr2 数组2
     * @param n 数组2的元素个数
     */
    public static void merge(int arr1[], int m, int arr2[], int n) {
        //1-先将数组A扩容到m+n的长度
//        for (int i = m; i < m+n; i++) {
//            arr1[i] = 0;
//        }
        //1-新建一个数组res
        int[] res = new int[m+n];
        //2-比较两个数组中的值，将较小值存储到A中
        int i = 0;
        int j = 0;
        int k = 0;
        while (true){
            if(i >= m || j >= n){
                break;
            }
            if(arr1[i] <= arr2[j]){
                res[k] = arr1[i];
                i++;
            }else{
                res[k] = arr2[j];
                j++;
            }
            k++;
        }
        //2-说明有一个已经循环结束了，直接将另一个数组的剩余部分写入到res中
        if(i==m){
            for (int l = j; l < n; l++) {
                res[k] = arr2[l];
                k++;
            }
        }
        if (j==n) {
            for (int l = i; l < m; l++) {
                res[k] = arr1[l];
                k++;
            }
        }
        //4-打印res值
        for (int l = 0; l < res.length; l++) {
            System.out.println(res[l]);
        }
        //5-，将res的值写回到arr1中
//        for (int l = 0; l < arr1.length; l++) {
//            arr1[l] = res[l];
//            System.out.println(arr1[l]);
//        }
    }
}
